﻿#define  _CRT_SECURE_NO_WARNINGS 1
//描述
//给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)
//，长度为n，反转该链表后，返回新链表的表头。
//
//数据范围： 0\leq n\leq10000≤n≤1000
//要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
//
//如当输入链表 {
//	1, 2, 3
//}时，
//经反转后，原链表变为{ 3,2,1 }，所以对应的输出为{ 3,2,1 }。
//以上转换过程如下图所示：
//
//
//struct ListNode* ReverseList(struct ListNode* pHead)
//{
//    if (pHead == NULL)
//        return NULL;
//    struct ListNode* prev = NULL;
//    struct ListNode* cur = pHead;
//    struct ListNode* After = pHead->next;
//    while (cur)
//    {
//        cur->next = prev;
//        prev = cur;
//        cur = After;
//        if (After)
//            After = After->next;
//    }
//    return prev;
//}


//描述
//输入两个递增的链表，单个链表的长度为n，
//合并这两个链表并使新链表中的节点仍然是递增排序的。
//数据范围： 0 \le n \le 10000≤n≤1000， - 1000 \le 
//节点值 \le 1000−1000≤节点值≤1000
//要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
//
//如输入 {
//	1, 3, 5
//}, { 2,4,6 }时，合并后的链表为{ 1,2,3,4,5,6 }，
//所以对应的输出为{ 1,2,3,4,5,6 }，转换过程如下图所示：
//
//struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
//    if (pHead1 == NULL)
//        return pHead2;
//    if (pHead2 == NULL)
//        return pHead1;
//    if (pHead1 && pHead2 == NULL)
//        return NULL;
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    while (pHead1 && pHead2)
//    {
//
//        if (pHead1->val < pHead2->val)
//        {
//            if (head == NULL)
//            {
//                head = tail = pHead1;
//            }
//            else
//            {
//                tail->next = pHead1;
//                tail = pHead1;
//            }
//            pHead1 = pHead1->next;
//        }
//        else
//        {
//            if (head == NULL)
//            {
//                head = tail = pHead2;
//            }
//            else
//            {
//                tail->next = pHead2;
//                tail = pHead2;
//            }
//            pHead2 = pHead2->next;
//
//        }
//    }
//    if (pHead1)
//    {
//        tail->next = pHead1;
//    }
//    if (pHead2)
//    {
//        tail->next = pHead2;
//    }
//
//    return head;
//
//}
//
//


//
//struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
//    if (pHead1 == NULL)
//        return pHead2;
//    if (pHead2 == NULL)
//        return pHead1;
//    if (pHead1 && pHead2 == NULL)
//        return NULL;
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    while (pHead1 && pHead2)
//    {
//        if (pHead1->val < pHead2->val)
//        {
//            tail->next = pHead1;
//            tail = pHead1;
//            pHead1 = pHead1->next;
//        }
//        else
//        {
//            tail->next = pHead2;
//            tail = pHead2;
//            pHead2 = pHead2->next;
//        }
//    }
//    if (pHead1)
//    {
//        tail->next = pHead1;
//    }
//    if (pHead2)
//    {
//        tail->next = pHead2;
//    }
//
//    struct ListNode* del = head;
//    head = head->next;
//    free(del);
//    return head;
//
//}
//
//
//
//
//struct ListNode* deleteNode(struct ListNode* head, int val)
//{
//    struct ListNode* prev = NULL;
//    struct ListNode* cur = head;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            if (prev == NULL)
//            {
//                cur = cur->next;
//                free(head);
//                head = cur;
//            }
//            else
//            {
//                prev->next = cur->next;
//                free(cur);
//                cur = prev->next;
//
//            }
//        }
//        else
//        {
//            prev = cur;
//            cur = cur->next;
//        }
//    }
//    return head;
//
//}

//
//#include <stdio.h>
//
//void func(int* a, int b[]) 
//{
//    b[0] = *a + 6; 
//}
//main() 
//{
//    int a, b[5];
//    a = 0;
//    b[0] = 3;
//    func(&a, b);
//    printf("%d\n", b[0]);
//}
//
//
//int main() 
//{
//    int x = 1, y = 0, a = 0, b = 0;
//    switch (x)
//    {
//    case 1:
//        switch (y) 
//        {
//        case 0:
//            a++;
//            break;
//        case 1:
//            b++;
//            break;
//        }
//    case 2:
//        a++;
//        b++;
//        break;
//    case 3:
//        a++;
//        b++;
//        break;
//    }
//    printf("a=%d,b=%d\n", a, b);
//}


//
//#include <stdio.h>
//#define N 2
//#define M N + 1
//#define NUM (M + 1) * M / 2
//main() { printf("%d\n", NUM); }
//
//(2+1+1)*2+1/2


//switch (i)
//{
//case 1: i++; 
//case 2: i--;
//case 3: ++i; 
//	break;
//case 4: --i;
//default: i++;
//}
//
//
//struct complex 
//{
//    int real, unreal;
//
//} data1 = { 1, 8 }, data2;

//
//
//
////int a = 5, 则++(a++)的值是 ?
//
//
//
//
//在声明类时，下面的说法正确的是（）
//
//A
//可以在类的声明中给数据成员赋初值（c++11新标准）
//B
//数据成员的数据类型可以是register
//C
//private、public、protected可以按任意顺序出现
//D
//没有用private、public、protected定义的数据成员是公有成员





//若链表中的某个节点，既不是链表头节点，
//也不是链表尾节点，则称其为该链表的「中间节点」。
//
//假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
//
//例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），
//将其删除后，剩余链表为 a->b->d->e->f


///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//void deleteNode(struct ListNode* node)
//{
//    struct ListNode* next = node->next;
//    node->val = next->val;
//    node->next = next->next;
//    free(next);
//}


//
//给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。
//已知此链表是一个整数数字的二进制表示形式。
//
//请你返回该链表所表示数字的 十进制值 。
//
//

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//int getDecimalValue(struct ListNode* head)
//{
//    struct ListNode* cur = head;
//    int count = 0;
//    while (cur)
//    {
//        count++;
//        cur = cur->next;
//    }
//    cur = head;
//    int sum = 0;
//    while (cur)
//    {
//        sum += (cur->val) * (int)pow(2, count - 1);
//        count--;
//        cur = cur->next;
//    }
//
//    return sum;
//}
//实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
//注意：本题相对原题稍作改动
//示例：
//输入： 1->2->3->4->5 和 k = 2
//输出： 4
//说明：
//给定的 k 保证是有效的。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     struct ListNode *next;
//  * };
//  */
////int kthToLast(struct ListNode* head, int k)
////{
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    int i = 0;
//    for (int i = 0; i < k; i++)
//    {
//        if (fast == NULL)
//            return NULL;
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//
//    return  slow->val;
////}
////
//
//    struct ListNode* reverseList(struct ListNode* head)
//    {
//        if (head == NULL)
//            return NULL;
//        struct ListNode* prev = NULL;
//        struct ListNode* cur = head;
//        struct ListNode* next = cur->next;
//        while (cur)
//        {
//            cur->next = prev;
//            prev = cur;
//            cur = next;
//            if (next)
//            {
//                next = next->next;
//            }
//        }
//        return  prev;
//    }
//
//
//
//
//





/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
//示例:
//输入: 1->2->3->4->5->NULL
//输出 : 5->4->3->2->1->NULL
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//        return  NULL;
//    struct ListNode* cur = head;
//    struct ListNode* phead = NULL;
//    struct ListNode* next = cur->next;
//    while (cur)
//    {
//        cur->next = phead;
//        phead = cur;
//        cur = next;
//        if (next)
//            next = next->next;
//    }
//
//    return  phead;
//
//}


















